#ifndef MEMORY_POOL_H
#define MEMORY_POOL_H

#include <climits>
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <new>

template <typename T>
class MemoryPool
{
  public:
    /* Member types */
    typedef T               value_type;       		// T 的 value 类型
    typedef T*              pointer;          		// T 的 指针类型
    typedef T&              reference;        		// T 的引用类型
    typedef const T*        const_pointer;    		// T 的 const 指针类型
    typedef const T&        const_reference;  		// T 的 const 引用类型
    typedef std::size_t          size_type;        // size_t 类型
    typedef ptrdiff_t       difference_type; 	 // 指针减法结果类型

    // 这个来源于 allocate 的标准
    template <typename U> 
    struct rebind {
        typedef MemoryPool<U> other;
    };

    /* Member functions */
    /* 构造函数 */
    MemoryPool() {};   
    template <typename U> 
    MemoryPool(const MemoryPool<U> &diff_type) noexcept;  
	 
    /* 析构函数 */
    ~MemoryPool() {};
    
    /* 元素取址 */
    pointer address(reference _Val) const noexcept{
    	return &_Val;
	};
    const_pointer address(const_reference _Val) const noexcept{
    	return &_Val;
	};

    /* 分配函数 */
    pointer allocate(std::size_t _Count){
    	// 检查分配的内存大小是否超出了size_type所能表示的范围
    	if(_Count > size_type(-1) / sizeof(value_type)) {
			std::cout << "1"; 
			throw std::bad_alloc();
		}
        // 调用底层的分配函数来分配内存
		auto alloc_ptr = static_cast<pointer>(allocate0(_Count * sizeof(value_type)));
        // 检查分配是否成功
		if(alloc_ptr != NULL){
			return alloc_ptr;
		}
        else{
			std::cout << "2";
			throw std::bad_alloc();
		}
	};
	
	/* 释放函数 */
    void deallocate(pointer _Ptr, size_type _Count){
    	deallocate0(_Ptr, _Count);
	};
	
	// 使用placement new在指定位置构造对象
    template<class _Objty, class... _Types>
    void construct(_Objty *_Ptr, _Types&&... _Args){
        ::new (const_cast<void *>(static_cast<const volatile void *>(_Ptr)))_Objty(std::forward<_Types>(_Args)...);
    }
    
    // 销毁给定位置的对象
    template<class _Uty>
    void destroy(_Uty *_Ptr){
        _Ptr->~_Uty();
    }

  private:
	// 自由槽的联合体
	union FreeSlot{
        union FreeSlot *slot_next;	// 下一个自由槽指针
        char *data;	// 数据指针
    };
    typedef FreeSlot *FreeSlots;	// 自由槽指针类型

    static char *mempool_start;                             //指向内存池起始位置的指针
    static char *mempool_end;                               //指向内存池末尾位置的指针
    static std::size_t total_capc;                          //内存池的总容量
    static const int MAX_CAPC = 16384;                      //不使用 malloc 直接分配的最大块大小
    static const int blockSize = 64;                      //块的步长
    static FreeSlots volatile free_slot[MAX_CAPC/blockSize];	//自由槽数组
    
    static std::size_t FindIndex(std::size_t numBytes);     // 查找对应大小的自由槽索引
    static std::size_t FindAlign(std::size_t numBytes);     // 对齐内存，加快访问速度
    static char *AllocBlock(std::size_t size, int &num);    // 从内存池分配块
    static char *SupplyFreeSlot(std::size_t numBytes);      // 供给自由槽 

	static void *allocate0(std::size_t numBytes);			// 分配内存的底层函数
    static void deallocate0(void *p, std::size_t numBytes);	// 释放内存的底层函数
};
template <typename T>
char *MemoryPool<T>::mempool_start = nullptr;
template <typename T>
char *MemoryPool<T>::mempool_end = nullptr;
template <typename T>
std::size_t MemoryPool<T>::total_capc = 0;
template<typename T>
typename MemoryPool<T>::FreeSlots volatile MemoryPool<T>::free_slot[MemoryPool<T>::MAX_CAPC / MemoryPool<T>::blockSize] = { nullptr };


template <typename T>
void * MemoryPool<T>::allocate0(std::size_t numBytes){
    FreeSlots volatile *free_slot_temp;
    FreeSlots alloc_address = nullptr;
    void *return_address;

    // 若所需的字节数大于内存池的最大容量，使用 malloc 直接从内存中申请空间。 
    if(numBytes > (std::size_t)MAX_CAPC){
        return_address = std::malloc(numBytes);
        if(return_address == nullptr)	throw std::bad_alloc();
    }
    else{
    	// 从自由槽中寻找分配地址
    	free_slot_temp = free_slot + FindIndex(numBytes);
    	alloc_address = (*free_slot_temp);
    	if(alloc_address != nullptr){
        	return_address = alloc_address;
    	}
    	else{
    		// 若自由槽中找不到合适地址，则从内存池中分配 
    		return_address = SupplyFreeSlot(FindAlign(numBytes));
		}
	}
    return return_address;
}

template <typename T>
void MemoryPool<T>::deallocate0(void *address_free, std::size_t numBytes){
    FreeSlots address_dealloc = (FreeSlots)address_free;
    FreeSlots volatile *free_slot_temp;
    // 若释放的字节数大于内存池的最大容量，使用 std::free 直接释放内存
    if(numBytes > (std::size_t)MAX_CAPC){
        std::free(address_free);
    }else{	// 否则释放到内存池中，加入合适的自由槽的头部 
        free_slot_temp = free_slot + FindIndex(numBytes);
        address_dealloc->slot_next = *free_slot_temp;
        *free_slot_temp = address_dealloc;
    }
}

template <typename T>
std::size_t inline MemoryPool<T>::FindIndex(std::size_t numBytes){
    // 找到合适的自由槽索引
	return (numBytes + blockSize - 1) / blockSize - 1;
}
template <typename T>
std::size_t inline MemoryPool<T>::FindAlign(std::size_t numBytes){
    // 找到对齐后的字节数
	return ((numBytes + blockSize - 1) & ~(blockSize - 1));
}

template <typename T>
char *MemoryPool<T>::AllocBlock(std::size_t numBytes, int &apply_num){
    char *return_address;
    std::size_t allocBytes = 0;
    std::size_t totalBytes = numBytes * apply_num;
    std::size_t leftBytes = mempool_end - mempool_start;

    // 内存池的剩余空间足够分配 totalBytes 
    if(leftBytes >= totalBytes){
    	// 直接从内存池中分配
        return_address = mempool_start;
        mempool_start += totalBytes;
    }
    // 内存池剩余空间不足，但至少可以分配一个块
    else if(leftBytes >= numBytes){
    	// 计算最多可分配的块数，然后从内存池中分配
        apply_num = leftBytes/numBytes;
        return_address = mempool_start;
        mempool_start = mempool_end;
    }
    // 无法从内存池中分配一个完整的块 
    else{
    	// 分配大小为 allocBytes 的新内存块，并将其加入自由槽链表中
        allocBytes = ((MAX_CAPC > totalBytes) ? MAX_CAPC : totalBytes) * 2;
        if(mempool_start != nullptr && allocBytes >0){
            FreeSlots volatile *free_slot_temp = free_slot + FindIndex(leftBytes);
            ((FreeSlots)mempool_start)->slot_next = *free_slot_temp;
            *free_slot_temp = (FreeSlots)mempool_start;
        }
        mempool_start = (char *)malloc(allocBytes);
        mempool_end = mempool_start + allocBytes;
        total_capc += allocBytes;
        return_address = AllocBlock(numBytes, apply_num);
    }
    return return_address;
}

template <typename T>
char *MemoryPool<T>::SupplyFreeSlot(std::size_t numBytes){
    int apply_num = 24;	// 一次申请 apply_num 个 numBytes，以减少频繁申请  
    FreeSlots volatile *free_slot_temp;
    FreeSlots alloc_address;
    char *return_address = AllocBlock(numBytes, apply_num); // 调用 AllocBlock 分配内存块
    if(apply_num != 1){  // 成功申请多于一个 numBytes 的内存块                                
        //将它们都连接到自由槽中
		free_slot_temp = free_slot + FindIndex(numBytes); 
        *free_slot_temp = alloc_address = (FreeSlots)((char *)return_address + numBytes);
        int count=1;
        do{
            alloc_address->slot_next = (FreeSlots)((char *)alloc_address + numBytes);
            alloc_address = alloc_address->slot_next;
        }while(count++ < apply_num-1);
        alloc_address->slot_next = nullptr;
    }

    return return_address;

}

template <class Tleft, class Tright>
bool operator==(const MemoryPool<Tleft> &lhs, const MemoryPool<Tright> &rhs) {
    return true;
}

template <class Tleft, class Tright>
bool operator!=(const MemoryPool<Tleft> &lhs, const MemoryPool<Tright> &rhs) {
    return false;
}

#endif // MEMORY_POOL_H


